package com.example.demo.node;

/**
 * 环形链表2
 *
 * @author GXYH
 * @date 2021/08/13
 */
public class CycleListNode2 {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        //定义两个指针从头开始走
        ListNode fast = head, slow = head;
        //如果有下一项一直走
        while (fast != null && fast.next != null) {
            //fast一次走两步
            fast = fast.next.next;
            //slow一次一部
            slow = slow.next;
            //如果相遇，证明有环
            //相遇时：慢指针走了a（头节点到环开始节点）+b步，快指针走了a+b+(b+c),(b+c)则是环长度，快指针速度为2倍慢指针，得到c=a;
            //再将慢指针或者快指针放到起点，一次走一步，因为c=a;所以相遇点必是环起点
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
